package com.love.labuladong.dynamic.rob;

import java.util.Arrays;

public class RobLCR089 {


    /**
     * 1.暴力递归 (思维版)
     * @param nums
     * @return
     */
    public static int rob(int[] nums){
        return process(nums,0,nums.length - 1);
    }


    // 定义 : 从第 i 家开始打劫，产生的最大价值
    // 定义几乎师最重要，也是最难的地方了
    public static int process(int[] nums,int i){
        if(i >= nums.length){
            return 0;
        }
        int ans = Math.max(
             // 不打劫，打下一家
             process(nums,i + 1),
             // 此家打劫，然后跳过下一家继续打劫
             nums[i] + process(nums,i+2)
        );
        return ans;
    }

    public static int process(int[] nums,int start,int end){
        if(start > end ){
            return 0;
        }

        int ans = Math.max(process(nums,start + 1,end), nums[start] + process(nums,start + 2,end));
        return ans;

    }

    // 总结：一维带数组动态规划，它的定义几乎都是从0位置开始，下标越界 base case 结束，牢记根据定义返回 base case 的值


    /**
     * 记忆化搜索
     * @param nums
     * @return
     */
    public static int robMemory(int[] nums){
        int[] dp= new int[nums.length + 2];
        Arrays.fill(dp,-1);

        return processMemory(nums,0,dp);
    }

    private static int processMemory(int[] nums, int i, int[] dp) {
        if(i >= nums.length){
            return 0;
        }
        int pass = dp[i+1] == -1 ? processMemory(nums,i+1,dp) : dp[i+1];
        int select = nums[i] + ((dp[i+2] == -1) ? processMemory(nums,i+2,dp) : dp[i+2]);

        int ans = Math.max(pass,select);
        dp[i] = ans;
        return ans;
    }

    /**
     * 严格位置依赖 : 从前面的结果推到后面的结果
     *
     * @param nums
     * @return
     */
    public static int robDistinct(int[] nums){
        //dp定义 ：到达 i 位置时的最大收益
        int n = nums.length;
        if(n == 1){
            return nums[0];
        }
        if(n == 2){
            return Math.max(nums[0],nums[1]);
        }
        int[] dp= new int[n];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0],nums[1]);
        for (int i = 2; i < nums.length; i++) {
            dp[i] = Math.max(dp[i-1],dp[i-2] + nums[i]);
        }
        return dp[nums.length - 1];
    }

    /**
     * 严格位置依赖 + 空间压缩
     * @param nums
     * @return
     */
    public static int robDistinctCompass(int[] nums){
        int n = nums.length;
        if(n == 1){
            return nums[0];
        }
        if(n == 2){
            return Math.max(nums[0],nums[1]);
        }
        // 定义 : 从 0 位置开始得到的最大收益，两个指针交替使用，推到后面的结果
        int start = nums[0];
        int last = Math.max(nums[0],nums[1]);
        int next = -1;
        for (int i = 2; i < n; i++) {
            next = Math.max(start + nums[i],last);
            start = last;
            last = next;
        }
        return next;
    }




    public static void main(String[] args) {
//        int[] nums = {1,2,3,1};
        int[] nums = {2,7,9,3,1};
        int rob = rob(nums);

        System.out.println(rob);
    }

}
